/*
 * @lc app=leetcode.cn id=31 lang=cpp
 *
 * [31] 下一个排列
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
   public:
    void nextPermutation(vector<int>& nums) {
        int length = nums.size();
        int left = 0;
        int right = 0;

        // 降序的开始节点
        for (int i = length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                left = i;
                break;
            }
        }

        if (left == 0) {
            // 不存在下一个更大的排列
            right = length - 1;
            while (left < right) {
                swap(nums[left], nums[right]);
                left++;
                right--;
            }
            return;
        } else {
            // 存在下一个更大的序列，寻找第一个比中间点大的点
            for (int i = length - 1; i >= left; i--) {
                if (nums[i] > nums[left - 1]) {
                    right = i;
                    break;
                }
            }
            swap(nums[left - 1], nums[right]);

            // left 之后的元素需要升序排序
            right = length - 1;
            while (left < right) {
                swap(nums[left], nums[right]);
                left++;
                right--;
            }
            
            return;
        }
    }
};
// @lc code=end
